package n1080;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int c[][]=new int[101][101];
	
	static int max=Integer.MIN_VALUE;
	static int la,lb;
	static String sa,sb;
	static int ss[][]={
		{5,-1,-2,-1,-3},
		{-1,5,-3,-2,-4},
		{-2,-3,5,-2,-2},
		{-1,-2,-2,5,-1},
		{-3,-4,-2,-1,Integer.MIN_VALUE},
	};
	static int getIndex(char c)
	{
		if(c=='A')return 0;
		if(c=='C')return 1;
		if(c=='G')return 2;
		if(c=='T')return 3;
		else return 4;
	}
	static void solve()
	{
		c[0][0]=0;
		for(int i=1;i<=la;i++){
			c[i][0]=c[i-1][0]+ss[getIndex(sa.charAt(i-1))][4];
		}
		for(int i=1;i<=lb;i++){
			c[0][i]=c[0][i-1]+ss[getIndex(sb.charAt(i-1))][4];
		}
		
		for(int i=1;i<=la;i++)
		{
			for(int j=1;j<=lb;j++)
			{
				int f1=c[i-1][j-1]+ss[getIndex(sa.charAt(i-1))][getIndex(sb.charAt(j-1))];
				int f2=c[i-1][j]+ss[getIndex(sa.charAt(i-1))][4];
				int f3=c[i][j-1]+ss[getIndex(sb.charAt(j-1))][4];
				c[i][j]=Math.max(Math.max(f1, f2), f3);
			}
		}
		System.out.println(c[la][lb]);
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub

		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(bf.readLine().trim());
		for(int i=0;i<n;i++)
		{
			StringTokenizer st=new StringTokenizer(bf.readLine().trim());
			la=Integer.parseInt(st.nextToken());
			sa=st.nextToken();
			st=new StringTokenizer(bf.readLine().trim());
			lb=Integer.parseInt(st.nextToken());
			sb=st.nextToken();
			solve();
		}
	}

}
